/**
 * 94. 二叉树的中序遍历
 * https://leetcode-cn.com/problems/binary-tree-inorder-traversal/
 */
const { createTreeNode, displayBaseArray } = require('../../libs/public');

// /**
//  * @param {TreeNode} node
//  * @param {number[]} result
//  */
// function recursive(node, result) {
//   if (node.left) recursive(node.left, result);
//   result.push(node.val);
//   if (node.right) recursive(node.right, result);
// }
//
// /**
//  * 递归
//  * @param {TreeNode} root
//  * @return {number[]}
//  */
// function inorderTraversal(root) {
//   if (!root) return [];
//   const result = [];
//   recursive(root, result);
//   return result;
// }

/**
 * 栈
 * @param {TreeNode} root
 * @return {number[]}
 */
function inorderTraversal(root) {
  if (!root) return [];
  const result = [];
  const stack = [];
  let node = root;
  while (node || stack.length) {
    while (node) {
      stack.push(node);
      node = node.left;
    }
    node = stack.pop();
    result.push(node.val);
    node = node.right;
  }
  return result;
}

console.log(displayBaseArray(inorderTraversal(createTreeNode([1, null, 2, 3]))) === '[1,3,2]');
console.log(displayBaseArray(inorderTraversal(createTreeNode([]))) === '[]');
console.log(displayBaseArray(inorderTraversal(createTreeNode([1]))) === '[1]');
console.log(displayBaseArray(inorderTraversal(createTreeNode([1, 2]))) === '[2,1]');
console.log(displayBaseArray(inorderTraversal(createTreeNode([1, null, 2]))) === '[1,2]');
